#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<int> smallestK(vector<int>& arr, int k)
    {
        srand(time(NULL));
        qsortFind(arr, 0, arr.size()-1, k);
        return {arr.begin(), arr.begin()+k};
    }

    void qsortFind(vector<int>& arr, int begin, int end, int k)
    {
        //begin==end是一个元素的情况，begin>end是arr为空的情况
        if(begin >= end)
            return;
        int key = getRandom(arr, begin, end);
        int left = begin-1, right = end+1, cur = begin;
        while(cur < right)
        {
            if(arr[cur] < key)
                swap(arr[cur++], arr[++left]);
            else if(arr[cur] == key)
                cur++;
            else
                swap(arr[cur], arr[--right]);
        }

        int a = left-begin+1, b = right-left-1;
        if(k < a)
            qsortFind(arr, begin, left, k);
        else if(k <= a+b)
            return;
        else
            qsortFind(arr, right, end, k-a-b);
    }

    static int getRandom(vector<int>& arr, int left, int right)
    {
        return arr[rand() % (right-left+1)+left];
    }
};